#include <iostream>
#include <string>
#include <vector>
#include <memory>
using namespace std;

class Solution {
public:
    const int MOD = 1000000007;
    int fib(int n) {
        if(n<2)
            return n;
        vector<vector<int>> a = {{1,1},{1,0}};
        auto ret = pow_m(a,n-1);
        return ret[0][0];
    }
    vector<vector<int>> pow_m(vector<vector<int>>& a, int n){
        vector<vector<int>> eye_m = {{1,0},{0,1}};
        vector<vector<int>> ret;
        while(n){
            if(n&1)
                ret = multiply_m(ret,a);
            a = multiply_m(a,a);
            n >>=1;
        }
        return ret;
    }
    vector<vector<int>> multiply_m(vector<vector<int>>& a, vector<vector<int>>& b){
        vector<vector<int>> ret(a);
        for(int i=0;i<a.size();i++){
            for(int j=0;j<a.size();j++){
                int temp = 0;
                for(int i_cal =0;i_cal<a.size();i_cal++)
                    temp = a[i][i_cal]*b[i_cal][j] + temp;
                ret[i][j] = temp%MOD;
            }
        }
        return ret;
    }
};

 
int main()
{
    Solution s;
    s.fib(2);
}

